Sous-chaînes et tranches

Table des matières

On considère $c = c_0c_1\dots c_n$ une chaîne de caractères de longueur $n+1$, dont les caractères sont $c_0,c_1,\dots,c_n$.

  1. On appelle préfixe de la chaîne $c$, toute chaîne de la forme $c_0c_1\dots c_i$, pour $i\in \db{0,n}$.
  2. On appelle suffixe de la chaîne $c$, toute chaîne de la forme $c_ic_{i+1}\dots c_n$, pour $i\in\db{0,n}$.

  3. On appelle sous-chaîne, ou facteur, de $c$ toute chaîne de la forme $c_ic_{i+1}\dots c_j$, pour $0\leq i\leq j\leq n$.

    On dit que cette sous-chaîne se trouve à la position ou l'indice $i$.

On convient que la chaîne vide "" est un préfixe, un suffixe et une sous-chaîne de toutes les chaînes de caractères.

Pour la chaîne "abracadabra"

1. Recherche d'une sous-chaîne dans un texte

Écrire une fonction est_prefixe qui prend en argument deux chaînes de caractères c1 et c2 et qui renvoie True ssi c1 est un préfixe de c2.

Préciser le nombre de comparaisons effectuées, dans le pire des cas, pour un appel sur des chaînes de longueurs $\l_1$ et $\l_2$.

  1. Écrire une fonction est_facteur qui prend en argument deux chaînes de caractères m (le motif) et t (le texte) et qui renvoie True ssi m est une sous-chaîne de t.

    Indication : Pour chaque indice $i$ possible dans le texte, on teste si le motif apparaît à cette position $i$, c'est-à-dire si m[0] == t[i] et m[1] == t[i+1], et m[2] == t[i+2], etc.

  2. Si $n$ est la longueur du texte, et $m$ celle de du motif, quel est, dans le pire des cas, le nombre de comparaisons effectuées ?

Il existe des algorithmes plus compliqués (Boyer-Moore, recherche par automate, Knuth–Morris–Pratt) qui garantissent une complexité en $O(n+m)$ opérations dans le pire des cas. Par contre, ces algorithmes nécessitent d'allouer $O(m)$ de mémoire supplémentaire (utilisation d'une liste de taille $m$ par exemple, pré-calculée à partir de m).

2. Tranches d'une chaîne de caractères ou d'une liste

Python dispose d'une syntaxe pour pouvoir copier une sous-chaîne d'une chaîne de caractère : si c est une chaîne de caractères, l'expression c[i:j] crée une nouvelle chaîne de caractères, contenant les caractères de c d'indices i (inclus) à j (exclus). En particulier, la longueur de c[i:j] est $j-i$.

Cette notion de tranches s'applique également à des listes. 

In [1]: c = "Essai"
In [2]: c[1:4]
Out[2]: "ssa"

In [1]: l = [0,1,2,3,4]
In [2]: l[2:len(l)]
Out[2]: [2,3,4]

La syntaxe l[i:j] admet les extensions suivantes :

  • Si i est omis, c'est qu'il vaut 0
  • Si j est omis, c'est qu'il vaut len(l)
  • Si i et j sont omis, l[:] donne une copie de toute la liste
  • j peut prendre des valeurs négatives, on compte alors à partir de la fin de la liste
In [1]: l = [3,5,7,11]
In [2]: l[:2]
Out[2]: [3,5]
In [3]: l[2:]
Out[3]: [7,11]

In [4]: l[:]
Out[4]: [3,5,7,11]
In [5]: l[:-1]
Out[5]: [3,5,7]

Écrire une fonction change_format qui prend en argument une chaîne de caractère représentant une date au format jj-mm-aaaa, comme "14-03-2001" et renvoie une chaîne de caractère représentant cette même date au format aaaa-mm-jj.

Réécrire la fonction est_facteur précédente, en utilisant la syntaxe de tranches. On utilisera des expressions c1 == c2 pour comparer des chaînes de caractères.

L'opérateur de comparaison == entre chaînes de caractères réalise autant de comparaisons élémentaires que l'implémentation naïve, qui compare caractère par caractère. Comme il cache une complexité algorithmique, il est à éviter, sauf invitation de l'énoncé.

Pour une liste, l'utilisation d'une tranche l[i:j] réalise une copie de la liste, avec une complexité en $O(j-i)$.

3. Exercices

3.1. Recherche de sous-chaînes

Écrire une fonction est_suffixe qui prend en argument deux chaînes de caractères c1 et c2 et qui renvoie True si c1 est un suffixe de c2.

Écrire une fonction long_prefix_com qui prend en argument deux chaînes c1 et c2 et renvoie la longueur d'un plus long préfixe commun à c1 et c2.

Écrire une fonction nb_occurrences qui prend en argument deux chaînes c1 et c2 et renvoie le nombre de fois où la chaîne c1 est présente dans la chaîne c2. Si c1 est une chaîne vide, la fonction nb_occurrences renverra len(c2) + 1.

On cherche compter le nombre d'apparitions d'un facteur simple, en minimisant le nombre de comparaisons entre caractères.

  1. Écrire une fonction nb_de_aaa qui prend en argument une chaîne c et renvoie le nombre d'occurrences du facteur "aaa" dans c. Si la chaîne c est de longueur $n$, votre fonction effectuera seulement $n$ comparaisons entre caractères dans le pire des cas.
  2. ★ Même chose, avec la chaîne "abc".

Écrire une fonction qui prend en argument une chaîne c et renvoie la plus grande valeur possible de $n$ pour laquelle c contient une sous-chaîne de la forme $a^n b^n = \underbrace{a\dots a}_{n} \underbrace{b\dots b}_{n}$. On pourra proposer une version qui ne lit la chaîne qu'une seule fois.

3.2. Utilisation de tranches

Écrire une fonction cycle qui prend en argument une chaîne de caractères c et renvoie la chaîne obtenue en mettant le premier caractère de c à la fin. Si c est la chaîne vide, on renverra la chaîne vide.

assert(cycle("abcd") == "bcda")

Écrire une fonction coupe qui prend en argument une chaîne de caractères c et renvoie un couple (c1,c2) de chaînes de caractères telles que c soit la concaténation de c1 et c2 et que len(c1) == len(c2) ou len(c1) == len(c2) + 1.

On écrira un jeu de deux tests.

Écrire une fonction split_space qui prend en argument une chaîne de caractères c et renvoie une liste de chaînes de caractères, obtenues en découpant la chaîne c à chaque caractère espace " ".

assert(split_space("ceci est un essai") == ["ceci", "est", "un", "essai"])

Écrire une fonction plps naïve qui prend en argument une chaîne c et renvoie la longueur du plus long préfixe propre de c (préfixe différent de tout c) qui soit également un suffixe de c.

  1. Écrire une fonction prefixes qui prend en argument une chaîne de caractères c et renvoie la liste de tous les préfixes de c.

    NB : La chaîne vide "" est un préfixe de toute chaîne.

  2. Écrire une fonction facteurs qui prend en argument une chaîne de caractères c et renvoie la liste de toutes les sous-chaînes de c (sans doublons). On ne demande pas d'optimiser la complexité.

3.3. Algorithme de Knuth-Moris-Pratt ★

La recherche naïve d'un motif m dans un texte t consiste à comparer le motif m à des tranches t[i:…] successives. Si lors d'une telle comparaison les $k$ premiers caractères de m coïncident avec le texte, on peut utiliser cette information pour éviter d'avoir besoin de comparer m à t[i+1:…], et sauter à t[i+j:m], pour une certaine valeur de j qui dépend de $k$. C'est le principe de l'algorithme KMP, qui commence par calculer une table de sauts (à partir de m), qui associe à $k$ la valeur $j$ du saut possible.

Par exemple, pour $\texttt{m} = \underset{0\,1\,2\,3\,4\,5}{\texttt{"ABUABD"}}$ de longueur $m=6$ dans le texte $\texttt{t} = \underset{0\,1\,2\,3\,4\,5\,6\,7\,8\,9\hspace{1em}}{\texttt{"ABCABUABUABD"}}$.

  • La comparaison de m avec t[0:6] échoue à l'indice 2 (caractère C).

    On sait à ce stade que la lettre à l'indice $1$ correspond (donc est un B). Comme B n'est pas un préfixe de m, la comparaison de m avec t[1:6] échouera forcément. On peut passer à la comparaison de m avec t[2:8] qui échoue alors au premier caractère.

  • La comparaison de m avec t[3:9] échoue à l'indice $8$ (lettre U au lieu de D).

    On sait à ce stade que la partie m[:5] = ABUAB correspond bien à t[3:8]

    La prochaine comparaison qui peut réussir est celle de m avec t[6:12], parce que AB est à la fois un préfixe de m, et un suffixe de m[:5].

En général, lors d'une comparaison de m avec t[i:…] qui échoue à l'indice k, avec $k\geq i+2$, la prochaine fenêtre à comparer sera t[i+j+1:…], où $j = k - i - \l$, où $\l$ est la longueur du plus long préfixe de m qui soit également un suffixe propre de m[:k-i] (c'est-à-dire un suffixe différent de tout m[:k-i]).

  1. Écrire une fonction plsp_naive qui prend en argument m et renvoie une liste l telle que, pour $2\leq i\leq m$, l[i] soit la longueur du plus long suffixe propre de m[:i] qui soit un préfixe de m.

  2. ★ Notons $c = \texttt{l[i]}$, $c' = \texttt{l[i+1]}$, p = m[:c], et p' = m[:c']. En remarquant entre autres que $c' \leq c+1$ et que p'[:-1] sera un préfixe et un suffixe de p, proposer une implémentation plus efficace. En particulier, une fois l[0], …, l[i] calculés, pour trouver l[i+1] on aura seulement besoin de comparer m[i+1] à certains autres caractères.

    ★ Justifier que la complexité est en $O(m)$.

  3. Implémenter l'algorithme KMP de recherche d'un motif dans un texte. Quelle est la complexité dans le pire des cas ?